数理逻辑

试试你东b的离散书，very good，离散总览

集合论：从集合到二元关系到函数

$$集合\stackrel{笛卡尔积}{\rightarrow}二元关系\stackrel{f(x)唯一}{\rightarrow}函数$$

代数系统：从二元关系到代数系统到群

$$二元关系+二元运算\stackrel{封闭性}{\rightarrow}代数系统\stackrel{特殊性质}{\rightarrow}群$$

数理逻辑

$$数理逻辑\begin{cases} 命题逻辑&(表面逻辑)\\\\ 谓词逻辑&(内部联系) \end{cases}$$

图论

$$图论\rightarrow\begin{cases} 各种图\\\\ 图的边、结点和度\\\\ 图的连通性、割集\\\\ 图的通路、回路\\\\ 欧拉图 \end{cases}$$

命题逻辑

命题公式

命题：能够确定真值的陈述句

连结词：非、合取、析取、蕴含、异或、等价

• 老哥，合取是 ∩，析取是 ∪，整本书学完了才发现理解反了
• 异或只在两个原子命题真值相异时真值为真，与等价存在非的关系
• 其中，非、合取、析取为基本连结词

命题公式：永真式、矛盾式、可满足式

命题范式

蕴含等值式

$$A\rightarrow B <=>\neg A\vee B$$

等值公式：德摩根式（合取和析取的转化）

$$\neg(A\wedge B)<=>\neg A \vee\neg B$$

化范式的常见步骤

• 通过德摩根律将所有连结词化为：合取、析取、非
• 通过分配律和结合律，将析取/合取小项结合

范式

• 合取范式：小项为析取式 ∪，通过合取 ∩ 连接
• 析取范式：小项为合取式 ∩，通过析取 ∪ 连接

通过真值表法构造合取/析取范式

• 合取范式：假中取假，析取相耦，合取相连
• 析取范式：真中取真，合取相耦，析取相连

比如有命题公式A->¬B，有真值表

A	B	A->¬B
0	0	1
0	1	1
1	0	1
1	1	0

合取范式：小项为析取式，全为假时项为假

• 取第四行，令每个原子命题均为 F，得合取范式¬A∪¬B

析取范式：小项为合取式，全为真时项为真

• 取 1、2、3 行，令原子命题均为真，则有三个小项¬A∩¬B、¬A∩B、A∩¬B
• 通过析取 ∪ 相连，得到析取范式(¬A∩¬B)∪(¬A∩B)∪(A∩¬B)

对于一般的情况，合取范式和析取范式可以通过分配律、结合律相互转化

推理规则

常用的推理规则

• 前提引入规则 P
• 结论引入规则 T
• 置换规则

真值表法

直接、间接证明法（推理的前提是条件永真）

• P 为条件
• T(1)(2) 表示当前命题公式（永真）由条件 1、2 推理得到

附加前提证明法（CP 规则）

$$A\wedge B\Rightarrow C\rightarrow D$$

等价于推理

$$A\wedge B\wedge C\Rightarrow D$$

此时有附加条件 C 为永真，只用推理出 D 永真，即可证明C->D永真

谓词逻辑

谓词和量词

谓词：由个体和谓词组成，如戴狗是个傻逼，个体就是戴狗，是个傻逼就是谓词，蕴含了逻辑

$$\forall x(F(x)\rightarrow G(x))$$

即对于所有 x，若 x 是戴狗 - F(x)，则 x 是傻逼 - G(x)

量词：全称量词（所有），存在量词（存在）

谓词公式：由谓词和量词构成的复合谓词

$$\neg \forall xF(x) \iff \exists x\neg F(x)$$

论域（个体域，个体所涉及的范围）和辖域（量词所作用的范围）

前束范式

谓词公式的前束范式：量词提到最前面，每个量词的辖域都是整个谓词公式

求前束范式的一般过程

1. 化蕴含：利用蕴含等值式（注意加括号）
2. 去括号前的非：德摩根律（展开式同样要加括号）
3. 去量词前的非：通过等价谓词转换
4. 换变量：如同时存在 ∀xF(x) ∪ ∃xG(x)，不妨将第二个个体换为 y，即 ∀xF(x) ∪ ∃yG(y)，此时可以直接往前提量词
5. 提量词：如上例，提为 ∀x∃y (F(x) ∪ G(y))

谓词的等价转换

不存在 F(x) = 全部都是 ¬F(x)

$$\neg\exists x F(x)<=>\forall x \neg F(x)$$

不全部都是 F(x) = 存在 ¬F(x)

$$\neg\forall xF(x)<=>\exists x\neg F(x)$$

还有一种情况，当给定了 x 的具体范围时，如 x ∈ {a, b}，有这样的列举等价

$$\forall x F(x)=F(a)∩F(b)\quad\exists xF(x)=F(a)∪F(b)$$

前束析取范式和前序合取范式同样可以通过分配律、结合律相互转化

谓词推理

US：全称指定规则

$$\forall x F(x)\Rightarrow F(a)$$

ES：存在指定规则

$$\exists x F(x)\Rightarrow F(b)$$

通过消去量词，将谓词逻辑转化为命题逻辑

UG：全称推广规则（证明中用的很少）

$$F(a)\Rightarrow \forall xF(x)$$

EG：存在推广规则

$$F(a)\Rightarrow \exists xF(x)$$

其实和命题推理的相仿，主要思路就是将谓词指定为命题逻辑，命题间证明后再推广回谓词逻辑，得以证明